package demo.DataStrucAndAlgo.Graph;

import java.util.Scanner;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/31-07-31-10:11
 * @Description：demo.DataStrucAndAlgo.Graph
 */
public class DFS_use {
    static int[][] map;
    static boolean[] isVisited;
    static int[] stack;
    static int top = 0,min_sum = 1000000,flag = -1;
    public DFS_use(int n){
        map = new int[n+1][n+1];          //map[i][j]为0表示i、j两点不通
        isVisited = new boolean[n];       //n个顶点是否被访问过
        stack = new int[n];              //记录从start能经过的顶点
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("分别输入顶点数n和路径数m：");
        int n = sc.nextInt();           //顶点数
        new DFS_use(n);
        int start = sc.nextInt();         //起点
        int end = sc.nextInt();          //终点
        int m = sc.nextInt();            //路径数
        System.out.println("输入m条路径");
        int x,y;
        for(int i = 0; i < m; i++){
            x = sc.nextInt();
            y = sc.nextInt();
            map[y][x] = map[x][y] = sc.nextInt();
        }
        dfs(start,n,end);
        System.out.printf("%d %d",min_sum,flag);
    }

    public static void dfs(int start, int n, int end) {          //从start点开始访问
        isVisited[start] = true;         //标记被访问过
        stack[top++] = start;            //经过的点记录到数组中
        if(start == end){           //到达终点
            int max = 0;
            int sum = 0,index = 0;          //sum路径的总权值，index记录用魔法棒的位置
            for (int i = 0; i < top - 1; i++) {
                sum = sum + map[stack[i]][stack[i+1]];      //权值相加
                if(max < map[stack[i]][stack[i+1]]){
                    max = map[stack[i]][stack[i+1]];           //魔法棒位置
                    index = stack[i];
                }
            }
            sum = sum -max;       //魔法棒用后的总权值
            if(min_sum > sum){       //找到最短路径
                min_sum = sum;
                flag = index;
            }else if(min_sum == sum && index < flag){
                flag = index;             //魔法棒位置
            }
            isVisited[start] = false;
            top--;
            return;
        }
        for (int i = 1; i <= n; i++) {     //遍历当前start能到达的点
            if(!isVisited[i] && map[start][i] != 0){
                dfs(i,n,end);  //递归遍历
            }
        }
        isVisited[start] = false;
        top--;
    }

}
